package club.xiaojiawei.array;

/**
 * @author 肖嘉威
 * @version 1.0
 * @date 2022/4/18 23:22
 * @question 844.比较含退格的字符串
 * @description 给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。
 * 注意：如果对空文本输入退格字符，文本继续为空。
 */
public class CompareString844 {
    public static void main(String[] args) {
        String t =  "ab##", s = "c#d#";
        System.out.println("是否匹配："+backspaceCompare1(s,t));
    }

    public static boolean backspaceCompare(String s, String t) {
        char[] sArr = s.toCharArray();
        char[] tArr = t.toCharArray();
        int step = 0;
        StringBuilder sBuilder = new StringBuilder();
        StringBuilder tBuilder = new StringBuilder();
        for (int i = sArr.length - 1; i >= 0; i--) {
            if (sArr[i] == '#'){
                step++;
            }else if (step != 0){
                step--;
            }else {
                sBuilder.append(sArr[i]);
            }
        }
        step = 0;
        for (int i = tArr.length - 1; i >= 0; i--) {
            if (tArr[i] == '#'){
                step++;
            }else if (step != 0){
                step--;
            }else {
                tBuilder.append(tArr[i]);
            }
        }
        return sBuilder.compareTo(tBuilder) == 0;
    }

    public static boolean backspaceCompare1(String s, String t) {
        char[] sArr = s.toCharArray();
        char[] tArr = t.toCharArray();
        StringBuilder sBuilder = new StringBuilder();
        StringBuilder tBuilder = new StringBuilder();
        int size = 0;
        for (int i = 0; i < sArr.length; i++) {
            if (sArr[i] == '#') {
                if (size > 0){
                    sBuilder.delete(size - 1, size--);
                }
            }else {
                size++;
                sBuilder.append(sArr[i]);
            }
        }
        size = 0;
        for (int i = 0; i < tArr.length; i++) {
            if (tArr[i] == '#') {
                if (size > 0){
                    tBuilder.delete(size - 1, size--);
                }
            }else {
                size++;
                tBuilder.append(tArr[i]);
            }
        }
        return sBuilder.toString().equals(tBuilder.toString());
    }
}
